<?php


$start_time = microtime();
$start_array = explode(" ",$start_time);
$start_time = ((float)$start_array[1] + (float)$start_array[0]);

$field = array(0 => array( 0 => 1, 1 => 1, 2 => 1, 3 => 1, 4 => 1),
               1 => array( 0 => 1, 1 => 1, 2 => 1, 3 => 1, 4 => 1),
               2 => array( 0 => 1, 1 => 0, 2 => 0, 3 => 0, 4 => 0),
               3 => array( 0 => 1, 1 => 1, 2 => 1, 3 => 1, 4 => 1),
               4 => array( 0 => 1, 1 => 1, 2 => 1, 3 => 1, 4 => 1));
               
function showit($field)
{
    for ($y = 0; $y <= 4; $y++)
    {
        for ($x = 0; $x <=4; $x++)
        {
            if ($x == 4) echo $field[$x][$y]."<br>";
            else echo $field[$x][$y];
        }
    }
}

function put_weight($field, $x, $y)
{
    $buf = array_fill(0, sizeof($field), array_fill(0, sizeof($field[0]), 0));
    $buf[$x][$y] = 1;
    $width = sizeof($field) - 1;
    $height = sizeof($field[0]) - 1;
        for ($poids = 1; $poids <= 1000; $poids++)
          {
            for ($y1 = 0; $y1<=$width; $y1++)
             {
                for ($x1 = 0; $x1<=$height; $x1++)
                
                    if ($buf[$x1][$y1] == $poids)
                    { 
                        //if (($x1 = 1) && ($y1 = 1))
                            //break 3;
                        if (isset($buf[$x1][$y1-1]))
                            if ($field[$x1][$y1-1])
                                if ($buf[$x1][$y1-1] == 0)
                                {
                                    $buf[$x1][$y1-1] = $poids+1;
                                    
                                    if (($x1 == 1) && (($y1-1) == 1 ))
                                        break 3;
                                }
                                        
                        if (isset($buf[$x1+1][$y1]))
                            if ($field[$x1+1][$y1])
                                if ($buf[$x1+1][$y1] == 0)
                                {
                                    $buf[$x1+1][$y1] = $poids+1;
                                    if ((($x1+1) == 1) && (($y1) == 1 ))
                                        break 3;
                                }
                        if (isset($buf[$x1][$y1+1]))
                            if ($field[$x1][$y1+1])
                                if ($buf[$x1][$y1+1] == 0)
                                {
                                    $buf[$x1][$y1+1] = $poids+1;
                                    if (($x1 == 1) && (($y1+1) == 1 ))
                                        break 3;
                                }
                        if (isset($buf[$x1-1][$y1]))
                            if ($field[$x1-1][$y1])
                                if ($buf[$x1-1][$y1] == 0)
                                {
                                    $buf[$x1-1][$y1] = $poids+1;
                                    if ((($x1-1) == 1) && (($y1) == 1 ))
                                        break 3;
                                }
    }
                 }   
                  
                //echo $poids." ";    
                }
                
            
            
            echo "<br>";
return $buf;
}

function GetPath($buf, $x, $y, $poids)
{
    if ($poids == 0)
    {
        
        return; 
    }
    else
    {
        //echo 'php';
        if ($buf[$x-1][$y] == $poids)
            return '('.($x-1).','.$y.')'.GetPath($buf, ($x-1), $y, ($poids - 1));
        if ($buf[$x+1][$y] == $poids)
            return '('.($x+1).','.$y.')'.GetPath($buf, ($x+1), $y, ($poids - 1));
        if ($buf[$x][$y-1] == $poids)
            return '('.($x).','.($y-1).')'.GetPath($buf, ($x), ($y-1), ($poids - 1));
        if ($buf[$x][$y+1] == $poids)
            return '('.($x).','.($y+1).')'.GetPath($buf, ($x), ($y+1), ($poids - 1));
    }
    
}
/*
echo sizeof($field[0]);
if (isset($field[44][0])) echo "wrong";
else echo "ok";*/
showit(put_weight($field, 3, 3));
echo '<br>';
$buff = (put_weight($field, 3, 3));
echo GetPath($buff,1,1,$buff[1][1] - 1);
//echo $field[0][0];
//var_dump($field);
echo "<br>";

$end_time = microtime();
$end_array = explode(" ",$end_time);
$end_time = ((float)$end_array[1] + (float)$end_array[0]);
$time = $end_time - $start_time;

echo sprintf("%1.4f",$time)."seconds";
?>
            
